TCAMs are typically used in routers and Ethernet switches for Internet protocol (IP) address forwarding. The storage elements are typically designed using a dynamic NOR/NAND type cell.
Content addressable memory (CAM) supports a read operation, write operation, and compare operation. A compare bus of the same width (e.g., bits per word) as an entry in the CAM is input at a clock edge. The data of the compare bus is simultaneously compared to every entry in the CAM. That is, the comparison occurs parallel so the bus may be compared to every entry in the CAM during one clock cycle. An entry is a match when every bit in an entry matches the corresponding bit in the compare bus. Alternatively, an entry is a mismatch when any bit in an entry does not match the corresponding bit in the compare bus. The bits of the entries in the CAM are either 0 or 1.
A TCAM is similar to CAM with the addition of a mask value that may be stored in a cell. The mask value may be referred to as a local mask. A mask value is not compared with a compare bit, and therefore, the compare result will always be a match.
FIG. 1 illustrates an architecture of a conventional TCAM 100. As illustrated in FIG. 1, a search word, such as “1101,” is input to a register 150 of the TCAM 100. The search word is compared to the value stored in the TCAM cells 110. TCAMs typically have sixteen TCAM cells per stage. The search is simultaneously conducted across the TCAM cells 110. The content of the TCAM cells 110 may be a high bit (1), a low bit (0), or a mask value (X). Prior to the search, a match line 130-136 for each set of TCAM cells 120-126 is set to high. The match lines 130-136 are input to a priority encoder 140. The TCAM 100 outputs (MLout) the address of the set of TCAM cells that match the search word line. Because the search is a parallel search, the search may be completed in one clock cycle. It should be noted that a mask value may be a 0 or 1, still, in the present disclosure, the mask value may be referred to as an X.
As an example, as illustrated in FIG. 1, a first set of TCAM cells 120 is set to “1 X 0 1,” a second set of TCAM cells 122 is set to “1 0 X 1,” a third set of TCAM cells 124 is set to “1 1 X X,” and a fourth set of TCAM cells 126 is set to “1 X 1 X.” When comparing the content of the TCAM cells to the search bit, when the content of the TCAM cell is a mask value X, the comparison will yield a match. Thus, according to the example illustrated in FIG. 1, the first set of TCAM cells 120 and the third set of TCAM cells 124 match the search word in the register 150. Accordingly, the match lines 130 134 of the first set of TCAM cells 120 and the third set of TCAM cells 124 will indicate a match and the priority encoder 140 outputs the address of the first set of TCAM cells 120 and the third set of TCAM cells 124.
The conventional TCAM architecture is a dynamic circuit and has a high dynamic power dissipation. In some cases, the TCAM may have a dynamic NAND architecture. In other cases, the TCAM may have a dynamic NOR architecture.
FIG. 2 illustrates a conventional dynamic NAND TCAM 200. As illustrated in FIG. 2, the dynamic NAND architecture 200 includes a match line MLNAND charged by a pre-charge line PRE# from a pull-up transistor 210. The match line MLNAND is connected to a series of intermediate match lines ML0-MLn−1. Each of the intermediate match lines ML0-MLn−1 is coupled to a mask cell Mask0-Maskn−1 and a key cell Key0-Keyn−1 via a transmission gate. The transmission gate includes a key NMOS transistor 202 coupled to a key cell Key0-Keyn−1 and a mask NMOS transistor 204 coupled to a mask cell Mask0-Maskn−1.
The content of the mask cells Mask0-Maskn−1 is illustrated in an expanded mask cell 222. As shown in the expanded mask cell 222, mask cells Mask0-Maskn−1 are SRAM cells including a mask value M, a mask value bar M#, a mask word line WLM, a mask bit line BLM, and a mask bit line bar BLM#. The content of the key cells Key0-Keyn−1 is illustrated in an expanded key cell 220. As shown in the expanded key cell 220, the key cells Key0-Keyn−1 are SRAM cells with XNOR logic. The key cells Key0-Keyn−1 further include a search line SL, a search line bar SL#, a key bit line BLK, a key bit line bar BLK#, a key value K, a key bar value K#, and a key write line WLK.
In a dynamic NAND TCAM architecture, the match lines are pre-charged high and evaluate low to indicate a match. That is, a pre-charge signal is used for each match line during every cycle to set the match lines to high. Depending on the status of the mask cell or key cell, the match line may be pulled low or remain high. Each intermediate match line is associated with a mask cell and a key cell. Furthermore, each key cell further includes XNOR logic. The dynamic NAND TCAM uses a serial operation. Thus, an intermediate match line (n−1) may discharge (e.g., compare with the value of the search line) when the previous intermediate match line (n−2) was pulled low to indicate a match. That is, the operation continues from one intermediate match line (n−2) to a subsequent intermediate match line (n−1) when there is a match and stops progressing through the intermediate match lines when there is a mismatch.
In a dynamic NOR TCAM architecture, match lines are pre-charged high and evaluate low to indicate a mismatch. The majority of comparisons yield a mismatch, and therefore, the dynamic NOR has an increased power consumption as a result of switching from high to low for indicating a mismatch. Furthermore, the dynamic NOR has a complex timing control because the pre-charge signal is used by each match line in each clock cycle.
FIG. 3 illustrates a conventional dynamic NOR TCAM 300. As illustrated in FIG. 3, the dynamic NOR TCAM 300 includes key cells Key0-Keyn−1 and mask cells Mask0-Maskn−1. Typically, a NOR TCAM, such as the NOR TCAM 300 of FIG. 3, may have sixteen key and mask cells. Data is input via search lines (SL0-SLn−1 and SL0#-SLn−1#). The data is compared to the values stored in the key cells Key0-Keyn−1 and mask cells Mask0-Maskn−1. The match line MLNOR and search lines (SL0-SLn−1 and SL0#-SLn−1#) are pre-charged high via the pre-charge line PRE# from a pull-up transistor 303. The match line MLNOR will evaluate low when there is a mismatch between the data input via one of the search lines (SL0-SLn−1 and SL0#-SLn−1#) and the data stored in one of the cells Key0-Keyn−1 Mask0-Maskn−1. The match line remains high when the values of all of the cells Key0-Keyn−1 Mask0-Maskn−1 match the input data.
The structure of the key cells Key0-Keyn−1 is illustrated in the expanded key cell 330 and the structure of the mask cells Mask0-Maskn−1 is illustrated in the expanded mask cell 333. As illustrated in the expanded key cell 330, the key cells Key0-Keyn−1 are implemented via an SRAM cell. During a compare operation, the key bar K# is ANDed with the search line SL. The key cells Key0-Keyn−1 include a bit line BLK, a bit line bar BLK#, and a word line WLK.
As illustrated in the expanded mask cell 333, the mask cells Mask0-Maskn−1 are implemented via a SRAM cell. During a comparison operation, the mask bar M# is ANDed with the search line bar SL#. The mask cells Mask0-Maskn−1 include a bit line BLM, a bit line bar BLM#, and a word line WLM.
TABLE 1 is a truth table for the dynamic NOR TCAM. TABLE 1 shows the value of the match line based on the values of the mask cells (M), key cells (K), and the search lines (SL and SL#). It should be noted that the state refers to the state of a storage element (key cell and mask cell). The state is 0 when the key bit has a value of 0, the state is 1 when the key bit has a value of 1, and the state is X when both the mask bit and the key bit are 1. The state of X refers to a mask state in which there is neither a match nor a mismatch, rather, there is no comparison between the value of the search line and the values of the mask cell and key cell. Thus, the match line always indicates a match.
TABLE 1SearchMask BitKey BitSearchLine BarMatch LineState(M)(K)Line (SL)(SL#)(MLNOR)010011010100101010101101X11XX1—00——Not Allowed
As shown in TABLE 1, the match line will be 0 (low) and indicate a mismatch when the key bit and search line have different values. Likewise, the match line will be 0 and indicate a mismatch when both the mask bit and search line bar have different values. That is, when the key bit is 0 (e.g., key bit bar (K#) is 1) and the search line is 1 or when the mask bit is 0 (e.g., mask bit bar (M#) is 1) and the search line bar is 1, a pull down transistor will be activated to pull the match line to low. Moreover, the match line will be 1 (high) and indicate a match when the key bit and search line have the same values. Likewise, the match line will be 1 and indicate a match when both the mask bit and search line bar have the same values. Furthermore, when both the mask bit and key bit are 1, the state is X. That is, the match line will remain high and indicate a match regardless of the value of the search line.
As discussed above, in a dynamic NOR TCAM, the match lines and search lines are pre-charged high at the beginning of every cycle and the match lines evaluate low to indicate a mismatch. The majority of comparisons of the cells in a TCAM yield a mismatch. Thus, the power consumption of the dynamic NOR TCAM is increased as a result of the switching from high to low when indicating a mismatch. In some cases, match lines may be pre-discharged low to reduce the power consumption. Still, even when then match lines are pre-discharged, a pre-charge operation charges the match line at the beginning of every cycle. Accordingly, the pre-charging of the match line leads to an increase in power consumption and additionally control circuitry.